// Author: Zhang, Yichao
// Date: 2009-12-3

#include "crossbit/VBlockAnalyzer.h"
#include <string.h>
using namespace std;
using namespace crossbit;

//#define DEBUG

// static members
bool VBlockAnalyzer::is_fft2d = false;
XTMemAddr VBlockAnalyzer::stream_start = 0x0;
XTMemAddr VBlockAnalyzer::stream_end = 0x0;

VBlockAnalyzer::VBlockAnalyzer()
{
	// empty
}

VBlockAnalyzer::VBlockAnalyzer(XTMemAddr ss, XTMemAddr se)
{
	stream_start = ss;
	stream_end = se;
}

VBlockAnalyzer::~VBlockAnalyzer()
{
	// empty
}

void VBlockAnalyzer::AddVBlockCount(XTMemAddr entry)
{
	if(entry >= stream_start && entry <= stream_end)
	{
		//block_count[entry]++;
		area_entries.insert(entry);
	}
}

void VBlockAnalyzer::FindLoop(XTMemAddr entry, XTMemAddr exit)
{
	if(		(entry >= stream_start && entry <= stream_end) &&
			(exit >= stream_start && exit <= stream_end)	)
	{
		if(exit <= entry)
		{
			loops[entry] = exit;
		}
	}
}

void VBlockAnalyzer::FindSpeedUpArea(VBlockBuilder *builder, Interpreter *interpreter)
{
	set<XTMemAddr>::iterator sit = area_entries.begin();
	while(sit != area_entries.end())
	{
		XTMemAddr next = *sit;
		builder->getReady(*sit);
		interpreter->setMode(PTX);
		while(!builder->isEnd())
		{
			next = interpreter->decode(next, builder);
		}
		hot_vblocks[*sit] = builder->wrapUp(next);
		sit++;
	}

#ifdef DEBUG
	map<XTMemAddr, XTMemAddr>::iterator mit = loops.begin();
	while(mit != loops.end())
	{
		if(mit->first >= stream_start && mit->first <= stream_end)
		{
			//printf("loop: entry = 0x%x, exit = 0x%x, count = %lld\n", mit->first, mit->second, block_count[mit->first]);
			printf("loop: entry = 0x%x, exit = 0x%x\n", mit->first, mit->second);
			/*
			XTMemAddr next = mit->first;
			builder->getReady(mit->first);
			interpreter->setMode(PTX);
			while(!builder->isEnd())
			{
				next = interpreter->decode(next, builder);
			}
			hot_vblocks[mit->first] = builder->wrapUp(next);;
			*/
		}
		mit++;
	}
#endif
}

void VBlockAnalyzer::__GetDefUseChain(XTMemAddr entry)
{
	for(int i = 0; i < use.size(); i++)
	{
		use[i].clear();
	}
	if(use.size() != 0) use.clear();
	for(int i = 0; i < def.size(); i++)
	{
		def[i].clear();
	}
	if(def.size() != 0) def.clear();
	def.resize(hot_vblocks[entry]->size());
	use.resize(hot_vblocks[entry]->size());
	int j = 0;
	VBlock::vb_iterator vit = hot_vblocks[entry]->begin();
	while(vit != hot_vblocks[entry]->end())
	{
		int n = (*vit)->getOperandNum();
		for(int k = 1; k <= n; k++)
		{
			Operand op = (*vit)->getOperand(k);
			if((op.type == Operand::VREG_DEF || op.type == Operand::SREG_DEF || op.type == Operand::FREG_DEF) && op.reg != -1)
			{
				def[j].push_back(op);
			}
			if((op.type == Operand::VREG_USE || op.type == Operand::SREG_USE || op.type == Operand::FREG_USE) && op.reg != -1)
			{
				use[j].push_back(op);
			}
		}
		vit++;
		j++;
	}
}

bool VBlockAnalyzer::__isSameOpr(const Operand lopr, const Operand ropr)
{
	return ( (lopr.reg == ropr.reg) && ((lopr.type == Operand::SREG_USE && ropr.type == Operand::SREG_DEF) || (lopr.type == Operand::SREG_DEF && ropr.type == Operand::SREG_USE) || (lopr.type == Operand::VREG_USE && ropr.type == Operand::VREG_DEF) || (lopr.type == Operand::VREG_DEF && ropr.type == Operand::VREG_USE) || (lopr.type == Operand::FREG_USE && ropr.type == Operand::FREG_DEF) || (lopr.type == Operand::FREG_DEF && ropr.type == Operand::FREG_USE)) );
	// old version, 2010-4-12
	//return ( (lopr.word == ropr.word) && ((lopr.type == Operand::SREG_USE && ropr.type == Operand::SREG_DEF) || (lopr.type == Operand::SREG_DEF && ropr.type == Operand::SREG_USE) || (lopr.type == Operand::VREG_USE && ropr.type == Operand::VREG_DEF) || (lopr.type == Operand::VREG_DEF && ropr.type == Operand::VREG_USE) || (lopr.type == Operand::FREG_USE && ropr.type == Operand::FREG_DEF) || (lopr.type == Operand::FREG_DEF && ropr.type == Operand::FREG_USE)) );
}

XTInt32 VBlockAnalyzer::__LookUpLatestDef(XTMemAddr entry, int &num, TRACE_NODE node, Operand &res, DataType &dt)
{
	for(int i = node.num - 1; i >= 0; i--)	// start from previous vinst, maybe problems here
	{
		for(int j = 0; j < def[i].size(); j++)
		{
			//printf("def.word = %d, def.type = %d, node.word = %d, node.type = %d\n", def[i][j].reg, def[i][j].type, node.opr.reg, node.opr.type);
			if(__isSameOpr(def[i][j], node.opr))
			//if(def[i][j] == node.opr)
			{
				Opcode opcode = hot_vblocks[entry]->getVInst(i)->getOpcode();
				res = def[i][j];
				num = i;
				dt = hot_vblocks[entry]->getVInst(i)->getDataType();
				if(opcode == OP_LI)
				{
					res = hot_vblocks[entry]->getVInst(i)->getOperand(1);
					return 1;
				}
				else if(opcode == OP_GET)
				{
					return 2;
				}
				else if(opcode == OP_LD)
					return 3;
				else
				{
					//op = hot_vblocks[entry]->getVInst(i)->getOpcode();
					return 0;
				}
			}
		}
	}
	return -1;
}

// added on 2010-4-12
void VBlockAnalyzer::__GetLDInfoGeneral(XTMemAddr entry)
{
	ld_info.clear();
	stack<TRACE_NODE> trace;
	VBlock::vb_iterator vit = hot_vblocks[entry]->begin();
	VAR_INFO source;	// should be only 1 source here
	int i = 0;		// VInst number
	while(vit != hot_vblocks[entry]->end())
	{
		Opcode op = (*vit)->getOpcode();
		DataType dt = (*vit)->getDataType();

		// all data-flow analyze based on LD analyze
		if(op == OP_LD)
		{
			//printf("---------Analyze LD No.%d, dt = %d-----------\n", i, dt);
			ld_info[i].dst = (*vit)->getOperand(3);
			ld_info[i].imm = (*vit)->getOperand(2).imm;
			TRACE_NODE *node = new TRACE_NODE(i, use[i][0]);
			trace.push( *node );
			int j = i;
			while(!trace.empty())
			{
				//printf("trace No.%d, opr.type = %d, opr.reg = %d....\n", trace.top().num, trace.top().opr.type, trace.top().opr.reg);
				Operand opr;
				DataType t;
				XTInt32 u = __LookUpLatestDef(entry, j, trace.top(), opr, t);

				switch(u)
				{
					case -1:	// def not found
						{
							assert(0 && "LD error!");
							break;
						}
					case 0:
						{
							trace.pop();
							for(int k = 0; k < use[j].size(); k++)
							{
								node = new TRACE_NODE(j, use[j][k]);
								trace.push(*node);
							}
							break;
						}
					case 1:	// LI
						{
							trace.pop();
							source.off = opr.imm;
							break;
						}
					case 2:	// GET
						{
							trace.pop();
							source.reg = use[j][0].reg;
							break;
						}
					case 3:	// LD
						{
							assert(0 && "shouldn't return 3 here!");
							break;
						}
				}
			}
			ld_info[i].src.push_back(source);
		}

		i++;
		vit++;
	}
}

void VBlockAnalyzer::__GetLDInfo(XTMemAddr entry)
{
	ld_info.clear();
	stack<TRACE_NODE> trace;
	VBlock::vb_iterator vit = hot_vblocks[entry]->begin();
	int i = 0;		// VInst number
	while(vit != hot_vblocks[entry]->end())
	{
		Opcode op = (*vit)->getOpcode();
		DataType dt = (*vit)->getDataType();

		// all data-flow analyze based on LD analyze
		if(op == OP_LD)
		{
			//printf("---------Analyze LD No.%d, dt = %d-----------\n", i, dt);
			ld_info[i].dst = (*vit)->getOperand(3);
			ld_info[i].imm = (*vit)->getOperand(2).imm;
			TRACE_NODE *node = new TRACE_NODE(i, use[i][0]);
			trace.push( *node );
			int j = i;
			while(!trace.empty())
			{
				//printf("trace No.%d, opr.type = %d, opr.reg = %d....\n", trace.top().num, trace.top().opr.type, trace.top().opr.reg);
				Operand opr;
				DataType t;
				XTInt32 u = __LookUpLatestDef(entry, j, trace.top(), opr, t);

				switch(u)
				{
					case -1:	// def not found
						{
							assert(0 && "LD error!");
							break;
						}
					case 0:
						{
							trace.pop();
							//operators[i].push(op);
							for(int k = 0; k < use[j].size(); k++)
							{
								node = new TRACE_NODE(j, use[j][k]);
								trace.push(*node);
							}
							break;
						}
					case 1:	// LI
						{
							// it seems LI inst come first all the time
							// and if VAR_INFO is modified later, there will be a segmentation fault...
							// so I set reg = 5 directly here...
							ld_info[i].src.push_back(VAR_INFO(5, opr.imm));
							trace.pop();
							break;
						}
					case 2:	// GET
						{
							trace.pop();
							if(use[j][0].reg == 5)
							{
							//ld_info[i].src.push_back(VAR_INFO(use[j][0].reg, -1));
							}
							else
							{
								node = new TRACE_NODE(j, use[j][0]);
								trace.push(*node);
							}
							break;
						}
					case 3:	// LD
						{
							//assert(0 && "shouldn't return 3 here!");
							trace.pop();
							if(ld_info[j].src[0].reg == 5)
							{
								//printf("ld_src pushed: s%d:0x%x\n", ld_info[j].src[0].reg, ld_info[j].src[0].off);
								ld_info[i].src.push_back(ld_info[j].src[0]);
							}
							break;
						}
				}
			}
		}

		i++;
		vit++;
	}
}

void VBlockAnalyzer::__GetLoopInfo(XTMemAddr entry)
{
	stack<TRACE_NODE> trace;
	LOOP_INFO cur_loop;

	VBlock::vb_iterator vit = hot_vblocks[entry]->begin();
	cur_loop.entry = loops[entry];
	cur_loop.range = entry - loops[entry];

	int i = 0;		// VInst number
	while(vit != hot_vblocks[entry]->end())
	{
		Opcode op = (*vit)->getOpcode();
		DataType dt = (*vit)->getDataType();

		// find out loop index and loop bound
		if(op == OP_BRANCH)
		{
			//printf("---------Analyze BRANCH No.%d-----------\n", i);
			TRACE_NODE *node;
			bool flag = false;
			for(int k = 0; k < use[i].size(); k++)
			{
				if(use[i][k].reg != 0)
				{
					node = new TRACE_NODE(i, use[i][k]);
					trace.push(*node);
				}
			}

			int j = i;
			while(!trace.empty())
			{
				Operand opr;
				DataType t;
				XTInt32 u = __LookUpLatestDef(entry, j, trace.top(), opr, t);

				switch(u)
				{
					case -1:	// not found
						trace.pop();
						break;
					case 0:		// regular
						trace.pop();
						for(int k = 0; k < use[j].size(); k++)
						{
							node = new TRACE_NODE(j, use[j][k]);
							if(!((node->opr).type == Operand::VREG_USE && (node->opr).reg == 0))
							{
								trace.push(*node);
							}
						}
						break;
					case 1:		// LI
						trace.pop();
						break;
					case 2:		// GET
						trace.pop();
						node = new TRACE_NODE(j, use[j][0]);
						trace.push(*node);
						break;
					case 3:		// LD
						{
							trace.pop();
							for(int k = 0; k < ld_info[j].src.size(); k++)
							{
								if(ld_info[j].src[k].reg == 5)
								{
									flag = true;
									if(ld_info[j].src[k].off > 0)	// bound
									{
										cur_loop.bound.reg = 5;
										cur_loop.bound.off = ld_info[j].src[k].off;
									}
									else							// index
									{
										cur_loop.index.reg = 5;
										cur_loop.index.off = ld_info[j].src[k].off;
									}
								}
								else
								{
									flag = false;
									Operand temp_opr(Operand::SREG_USE);
									temp_opr.reg = ld_info[j].src[k].reg;
									trace.push(TRACE_NODE(j, temp_opr));
								}
							}
							break;
						}
				}
			}
			//printf("cur_loop entry: 0x%x, index: s%d:0x%x, bound: s%d:%x\n", cur_loop.entry, cur_loop.index.reg, cur_loop.index.off, cur_loop.bound.reg, cur_loop.bound.off);
			if(cur_loop.index.reg == 5 && cur_loop.bound.reg == 5)
			{
				loop_info.push_back(cur_loop);
			}
		}
		i++;
		vit++;
	}
}

void VBlockAnalyzer::__GetDataInfo(XTMemAddr entry)
{
	st_info.clear();
	//printf("==============GetDataInfo from 0x%x================\n", entry);
	stack<TRACE_NODE> trace;

	VBlock::vb_iterator vit = hot_vblocks[entry]->begin();
	int i = 0;		// VInst number
	while(vit != hot_vblocks[entry]->end())
	{
		Opcode op = (*vit)->getOpcode();
		DataType dt = (*vit)->getDataType();

		// find out P and temp_var
		if(op == OP_ST)
		{
			bool ebp_flag = false;
			//printf("---------Analyze ST No.%d-----------\n", i);
			TRACE_NODE *node;
			if(use[i][1].reg != 0)
			{
				node = new TRACE_NODE(i, use[i][1]);
				trace.push(*node);
			}

			int j = i;
			while(!trace.empty())
			{
				//printf("........trace No.%d........\n", j);
				Operand opr;
				DataType t;
				XTInt32 u = __LookUpLatestDef(entry, j, trace.top(), opr, t);

				switch(u)
				{
					case -1:	// not found
						assert(0 && "should always found!");
						trace.pop();
						break;
					case 0:		// regular
						trace.pop();
						for(int k = 0; k < use[j].size(); k++)
						{
							node = new TRACE_NODE(j, use[j][k]);
							trace.push(*node);
						}
						break;
					case 1:		// LI
						if(ebp_flag)
						{
							st_info[i].dst.push_back(VAR_INFO(5, opr.imm));
							temp_var.push_back(VAR_INFO(5, opr.imm));
						}
						trace.pop();
						break;
					case 2:		// GET
						trace.pop();
						if(use[j][0].reg != 5)
						{
							node = new TRACE_NODE(j, use[j][0]);
							trace.push(*node);
						}
						else
						{
							ebp_flag = true;
						}
						break;
					case 3:		// LD
						{
							trace.pop();
							for(int k = 0; k < ld_info[j].src.size(); k++)
							{
								if(ld_info[j].src[k].reg == 5)
								{
									temp_var.push_back(VAR_INFO(5, ld_info[j].src[k].off));
								}
								else
								{
									Operand temp_opr(Operand::SREG_USE);
									temp_opr.reg = ld_info[j].src[k].reg;
									trace.push(TRACE_NODE(j, temp_opr));
								}
							}
							break;
						}
				}
			}
		}// end of OP_ST

		if( !is_fft2d )
		{
		// find out MUL.f64's operands' source address
		if(op == OP_MUL && dt == f64)
		{
			//printf("---------Analyze FMUL No.%d-----------\n", i);
			TRACE_NODE *node;
			for(int k = 0; k < use[i].size(); k++)
			{
				node = new TRACE_NODE(i, use[i][k]);
				trace.push(*node);
			}

			int j = i;
			bool flag;
			while(!trace.empty())
			{
				//printf("trace No.%d, opr.type = %d, opr.reg = %d....\n", trace.top().num, trace.top().opr.type, trace.top().opr.reg);
				Operand opr;
				DataType t;
				XTInt32 u = __LookUpLatestDef(entry, j, trace.top(), opr, t);

				switch(u)
				{
					case -1:	// not found
						assert(0 && "should always found!");
						break;
					case 0:		// regular
						trace.pop();
						for(int k = 0; k < use[j].size(); k++)
						{
							node = new TRACE_NODE(j, use[j][k]);
							trace.push(*node);
						}
						break;
					case 1:		// LI
						trace.pop();
						break;
					case 2:		// GET
						trace.pop();
						if(t == f64)
						{
							node = new TRACE_NODE(j, use[j][0]);
							trace.push(*node);
						}
						break;
					case 3:		// LD
						{
							trace.pop();
							for(int k = 0; k < ld_info[j].src.size(); k++)
							{
								if(ld_info[j].src[k].reg == 5)
								{
									if(ld_info[j].src[k].off > 0x2)		//XXX: cao a....
									{
										//printf("matrix_base pushed from No.%d: s%d:0x%x\n", j, ld_info[j].src[k].reg, ld_info[j].src[k].off);
										matrix_base.push_back(VAR_INFO(5, ld_info[j].src[k].off));
									}
									else
									{
										//printf("LD src = s%d:0x%x\n", ld_info[j].src[k].reg, ld_info[j].src[k].off);
										map<XTInt32, ST_INFO>::iterator st_it = st_info.begin();
										while(st_it != st_info.end())
										{
											//printf("ST dst = s%d:0x%x\n", (st_it->second).dst[0].reg, (st_it->second).dst[0].off);
											if((st_it->second).dst[0] == ld_info[j].src[k])
											{
												//printf("FOUND No.%d!\n", st_it->first);
												node = new TRACE_NODE(st_it->first, use[st_it->first][0]);
												trace.push(*node);
												break;
											}
											st_it++;
										}
									}
								}
								else
								{
									//XXX: must be SREG_USE???
									Operand temp_opr(Operand::SREG_USE);
									temp_opr.reg = ld_info[j].src[k].reg;
									trace.push(TRACE_NODE(j, temp_opr));
								}
							}
							break;
						}
				}
			}
		}
		}

		i++;
		vit++;
	}
}

void VBlockAnalyzer::AnalyzeVBlockDataFlow(XTMemAddr entry)
{
	//printf("===========ADF 0x%x============\n", entry);
	// Start from LD VInsts, find where the target address come from.
	//map<XTInt32, LD_INFO> ld_info;		// map<VInst No. , LD_INFO>
	//map<XTInt32, ST_INFO> st_info;		// map<VInst No. , ST_INFO>
	stack<TRACE_NODE> trace;			// analyze trace
	map<XTInt32, queue<Opcode> > operators;			// arithmetic operators queue
	LOOP_INFO cur_loop;					// current loop information

	VBlock::vb_iterator vit = hot_vblocks[entry]->begin();
	cur_loop.entry = loops[entry];
	//cur_loop.count = block_count[entry];
	cur_loop.range = entry - loops[entry];
	int i = 0;		// VInst number
	while(vit != hot_vblocks[entry]->end())
	{
		Opcode op = (*vit)->getOpcode();
		DataType dt = (*vit)->getDataType();

		// all data-flow analyze based on LD analyze
		if(op == OP_LD)
		{
			//printf("---------Analyze LD No.%d, dt = %d-----------\n", i, dt);
			ld_info[i].dst = (*vit)->getOperand(3);
			ld_info[i].imm = (*vit)->getOperand(2).imm;
			TRACE_NODE *node = new TRACE_NODE(i, use[i][0]);
			trace.push( *node );
			int j = i;
			while(!trace.empty())
			{
				//printf("trace No.%d, opr.type = %d, opr.reg = %d....\n", trace.top().num, trace.top().opr.type, trace.top().opr.reg);
				Operand opr;
				DataType t;
				XTInt32 u = __LookUpLatestDef(entry, j, trace.top(), opr, t);

				switch(u)
				{
					case -1:	// def not found
						{
							assert(0 && "LD error!");
							break;
						}
					case 0:
						{
							trace.pop();
							//operators[i].push(op);
							for(int k = 0; k < use[j].size(); k++)
							{
								node = new TRACE_NODE(j, use[j][k]);
								trace.push(*node);
							}
							break;
						}
					case 1:	// LI
						{
							// it seems LI inst come first all the time
							// and if VAR_INFO is modified later, there will be a segmentation fault...
							// so I set reg = 5 directly here...
							ld_info[i].src.push_back(VAR_INFO(5, opr.imm));
							trace.pop();
							break;
						}
					case 2:	// GET
						{
							trace.pop();
							if(use[j][0].reg == 5)
							{
							//ld_info[i].src.push_back(VAR_INFO(use[j][0].reg, -1));
							}
							else
							{
								node = new TRACE_NODE(j, use[j][0]);
								trace.push(*node);
							}
							break;
						}
					case 3:	// LD
						{
							//assert(0 && "shouldn't return 3 here!");
							trace.pop();
							if(ld_info[j].src[0].reg == 5)
							{
								//printf("ld_src pushed: s%d:0x%x\n", ld_info[j].src[0].reg, ld_info[j].src[0].off);
								ld_info[i].src.push_back(ld_info[j].src[0]);
							}
							break;
						}
				}
			}
		}

		/*
		// find out width of Matrix A and Matrix B
		if(op == OP_MUL && dt == s32)
		{
			printf("---------Analyze MUL No.%d-----------\n", i);
			for(int k = 0; k < use[i].size(); k++)
			{
				trace.push(TRACE_NODE(i, use[i][k]));
			}

			int j = i;
			bool flag;
			while(!trace.empty())
			{
				Operand opr;
				Opcode op;
				DataType t;
				XTInt32 u = __LookUpLatestDef(entry, j, trace.top(), opr, op, t);

				switch(u)
				{
					case -1:
						assert(0 && "should always found!");
						trace.pop();
						break;
					case 0:
						trace.pop();
						for(int k = 0; k < use[j].size(); k++)
						{
							trace.push(TRACE_NODE(j, use[j][k]));
						}
						break;
					case 1:
						trace.pop();
						break;
					case 2:
						trace.pop();
						break;
					case 3:		// LD
						trace.pop();
						for(int k = 0; k < ld_info[j].src.size(); k++)
						{
							if(ld_info[j].src[k].reg == 5)	// EBP
							{
								if(ld_info[j].src[k].off > 0)	// a parameter of the func
								{
									//width.push_back(VAR_INFO(5, ld_info[j].src[k].off));
								}
							}
						}
						break;
				}
			}
		}
		*/

		// find out MUL.f64's operands' source address
		if(op == OP_MUL && dt == f64)
		{
			//printf("---------Analyze FMUL No.%d-----------\n", i);
			TRACE_NODE *node;
			for(int k = 0; k < use[i].size(); k++)
			{
				node = new TRACE_NODE(i, use[i][k]);
				trace.push(*node);
			}

			int j = i;
			bool flag;
			while(!trace.empty())
			{
				//printf("trace No.%d, opr.type = %d, opr.reg = %d....\n", trace.top().num, trace.top().opr.type, trace.top().opr.reg);
				Operand opr;
				DataType t;
				XTInt32 u = __LookUpLatestDef(entry, j, trace.top(), opr, t);

				switch(u)
				{
					case -1:	// not found
						assert(0 && "should always found!");
						break;
					case 0:		// regular
						trace.pop();
						for(int k = 0; k < use[j].size(); k++)
						{
							node = new TRACE_NODE(j, use[j][k]);
							trace.push(*node);
						}
						break;
					case 1:		// LI
						trace.pop();
						break;
					case 2:		// GET
						trace.pop();
						if(t == f64)
						{
							node = new TRACE_NODE(j, use[j][0]);
							trace.push(*node);
						}
						break;
					case 3:		// LD
						{
							trace.pop();
							for(int k = 0; k < ld_info[j].src.size(); k++)
							{
								if(ld_info[j].src[k].reg == 5)
								{
									if(ld_info[j].src[k].off > 0x2)		//XXX: cao a....
									{
										//printf("matrix_base pushed from No.%d: s%d:0x%x\n", j, ld_info[j].src[k].reg, ld_info[j].src[k].off);
										matrix_base.push_back(VAR_INFO(5, ld_info[j].src[k].off));
									}
									else
									{
										//printf("LD src = s%d:0x%x\n", ld_info[j].src[k].reg, ld_info[j].src[k].off);
										map<XTInt32, ST_INFO>::iterator st_it = st_info.begin();
										while(st_it != st_info.end())
										{
											//printf("ST dst = s%d:0x%x\n", (st_it->second).dst[0].reg, (st_it->second).dst[0].off);
											if((st_it->second).dst[0] == ld_info[j].src[k])
											{
												//printf("FOUND No.%d!\n", st_it->first);
												node = new TRACE_NODE(st_it->first, use[st_it->first][0]);
												trace.push(*node);
												break;
											}
											st_it++;
										}
									}
								}
								else
								{
									//XXX: must be SREG_USE???
									Operand temp_opr(Operand::SREG_USE);
									temp_opr.reg = ld_info[j].src[k].reg;
									trace.push(TRACE_NODE(j, temp_opr));
								}
							}
							break;
						}
				}
			}
		}

		// find out P and temp_var
		if(op == OP_ST)
		{
			bool ebp_flag = false;
			//printf("---------Analyze ST No.%d-----------\n", i);
			TRACE_NODE *node;
			if(use[i][1].reg != 0)
			{
				node = new TRACE_NODE(i, use[i][1]);
				trace.push(*node);
			}

			int j = i;
			while(!trace.empty())
			{
				Operand opr;
				DataType t;
				XTInt32 u = __LookUpLatestDef(entry, j, trace.top(), opr, t);

				switch(u)
				{
					case -1:	// not found
						assert(0 && "should always found!");
						trace.pop();
						break;
					case 0:		// regular
						trace.pop();
						for(int k = 0; k < use[j].size(); k++)
						{
							node = new TRACE_NODE(j, use[j][k]);
							trace.push(*node);
						}
						break;
					case 1:		// LI
						if(ebp_flag)
						{
							st_info[i].dst.push_back(VAR_INFO(5, opr.imm));
							temp_var.push_back(VAR_INFO(5, opr.imm));
						}
						trace.pop();
						break;
					case 2:		// GET
						trace.pop();
						if(use[j][0].reg != 5)
						{
							node = new TRACE_NODE(j, use[j][0]);
							trace.push(*node);
						}
						else
						{
							ebp_flag = true;
						}
						break;
					case 3:		// LD
						{
							trace.pop();
							for(int k = 0; k < ld_info[j].src.size(); k++)
							{
								if(ld_info[j].src[k].reg == 5)
								{
									temp_var.push_back(VAR_INFO(5, ld_info[j].src[k].off));
								}
								else
								{
									Operand temp_opr(Operand::SREG_USE);
									temp_opr.reg = ld_info[j].src[k].reg;
									trace.push(TRACE_NODE(j, temp_opr));
								}
							}
							break;
						}
				}
			}
		}// end of OP_ST

		// find out loop index and loop bound
		if(op == OP_BRANCH)
		{
			//printf("---------Analyze BRANCH No.%d-----------\n", i);
			TRACE_NODE *node;
			bool flag = false;
			for(int k = 0; k < use[i].size(); k++)
			{
				if(use[i][k].reg != 0)
				{
					node = new TRACE_NODE(i, use[i][k]);
					trace.push(*node);
				}
			}

			int j = i;
			while(!trace.empty())
			{
				Operand opr;
				DataType t;
				XTInt32 u = __LookUpLatestDef(entry, j, trace.top(), opr, t);

				switch(u)
				{
					case -1:	// not found
						trace.pop();
						break;
					case 0:		// regular
						trace.pop();
						for(int k = 0; k < use[j].size(); k++)
						{
							node = new TRACE_NODE(j, use[j][k]);
							if(!((node->opr).type == Operand::VREG_USE && (node->opr).reg == 0))
							{
								trace.push(*node);
							}
						}
						break;
					case 1:		// LI
						trace.pop();
						break;
					case 2:		// GET
						trace.pop();
						node = new TRACE_NODE(j, use[j][0]);
						trace.push(*node);
						break;
					case 3:		// LD
						{
							trace.pop();
							for(int k = 0; k < ld_info[j].src.size(); k++)
							{
								if(ld_info[j].src[k].reg == 5)
								{
									flag = true;
									if(ld_info[j].src[k].off > 0)	// bound
									{
										cur_loop.bound.reg = 5;
										cur_loop.bound.off = ld_info[j].src[k].off;
									}
									else							// index
									{
										cur_loop.index.reg = 5;
										cur_loop.index.off = ld_info[j].src[k].off;
									}
								}
								else
								{
									flag = false;
									Operand temp_opr(Operand::SREG_USE);
									temp_opr.reg = ld_info[j].src[k].reg;
									trace.push(TRACE_NODE(j, temp_opr));
								}
							}
							break;
						}
				}
			}
			//printf("cur_loop entry: 0x%x, index: s%d:0x%x, bound: s%d:%x\n", cur_loop.entry, cur_loop.index.reg, cur_loop.index.off, cur_loop.bound.reg, cur_loop.bound.off);
			if(cur_loop.index.reg == 5 && cur_loop.bound.reg == 5)
			{
				loop_info.push_back(cur_loop);
			}
		}
		i++;
		vit++;
	}
}

void VBlockAnalyzer::__ProfileCollector()
{
	int r_idx = 0;
#ifdef DEBUG
	printf("============loop size = %d==============\n", loop_info.size());
#endif

	// sort the loop info
	stable_sort(loop_info.begin(), loop_info.end());
	loop_info.erase(unique(loop_info.begin(), loop_info.end()), loop_info.end());

	// display loop info
	for(int i = 0; i < loop_info.size(); i++)
	{
#ifdef DEBUG
		printf("loop No.%d, index s%d:0x%x, bound s%d:0x%x, entry 0x%x, range %d\n", i, loop_info[i].index.reg, loop_info[i].index.off, loop_info[i].bound.reg, loop_info[i].bound.off, loop_info[i].entry, loop_info[i].range);
#endif
		index.push_back(loop_info[i].index);
	}

	// merge loop index
	sort(index.begin(), index.end());
	index.erase(unique(index.begin(), index.end()), index.end());

	/////////////////////////////////////////////////////////////////////////
	// TODO: temp algorithm to find inner and outer loop
	vector<XTUint64> temp_range(index.size());
	for(int i = 0; i < index.size(); i++)
	{
		//temp_range[i] = 0;
		for(int j = 0; j < loop_info.size(); j++)
		{
			if(index[i] == loop_info[j].index)
				temp_range[i] = loop_info[j].range;
		}
	}
	vector<INDEX_RANGE> temp_idx_range;
	for(int i = 0; i < index.size(); i++)
	{
		temp_idx_range.push_back(INDEX_RANGE(index[i], temp_range[i]));
	}
	sort(temp_idx_range.begin(), temp_idx_range.end());
	index.clear();
	for(int i = temp_idx_range.size() - 1; i >= 0; i--)
	{
		index.push_back(temp_idx_range[i].index);
	}
	/////////////////////////////////////////////////////////////////////////
#ifdef DEBUG
	printf("============index size = %d==============\n", index.size());
#endif

	char i_label[4][5] = {"TidX", "TidY", "TidZ", "TidA"};
	for(int i = 0; i < index.size(); i++)
	{
		int direction = 0;
		if(i == 0) direction = 2;
#ifdef DEBUG
		printf("index No.%d, s%d:0x%x\n",i, index[i].reg, index[i].off);
#endif
		records.push_back(Record(direction, index[i].reg, index[i].off, i_label[i], sizeof(int), r_idx++));
	}
	r_idx = 4;

	vector<VAR_INFO> temp_width;
	// Get Width and Height from Loop bounds
	for(int j = 0; j < loop_info.size(); j++)
	{
		temp_width.push_back(loop_info[j].bound);
	}

	sort(temp_width.begin(), temp_width.end());
	temp_width.erase(unique(temp_width.begin(), temp_width.end()), temp_width.end());

	vector<VAR_INFO>::iterator mit = matrix_base.begin();
	while(mit != matrix_base.end())
	{
		vector<VAR_INFO>::iterator wit = find(temp_width.begin(), temp_width.end(), *mit);
		if(temp_width.end() != wit)
		{
			width.push_back(*mit);
			matrix_base.erase(mit);
		}
		else
			mit++;
	}

	// delete width from temp_width
	vector<VAR_INFO>::iterator temp_it = temp_width.begin();
	while(temp_it != temp_width.end())
	{
		vector<VAR_INFO>::iterator width_it = find(width.begin(), width.end(), *temp_it);
		if(width.end() != width_it)
		{
			temp_width.erase(temp_it);
		}
		else
			temp_it++;
	}

	// merge temp_var
	sort(temp_var.begin(), temp_var.end());
	temp_var.erase(unique(temp_var.begin(), temp_var.end()), temp_var.end());

	temp_it = temp_var.begin();
	while(temp_it != temp_var.end())
	{
		if(width.end() != find(width.begin(), width.end(), *temp_it))
		{
			temp_var.erase(temp_it);
		}
		else if(index.end() != find(index.begin(), index.end(), *temp_it))
		{
			temp_var.erase(temp_it);
		}
		else if(temp_it->off > 0)
		{
			if(!binary_search(matrix_base.begin(), matrix_base.end(), *temp_it))
			{
				if( !is_fft2d )
					matrix_base.push_back(*temp_it);
			}
			temp_var.erase(temp_it);
		}
		else
			temp_it++;
	}

	/*
	printf("<<<<<<<<<<<<<<temp_var size = %d>>>>>>>>>>>>>>>>>\n", temp_var.size());
	for(int i = 0; i < temp_var.size(); i++)
	{
		printf("temp_var[%d]: s%d:0x%x\n", i, temp_var[i].reg, temp_var[i].off);
	}

	printf("<<<<<<<<<<<<<<temp_width size = %d>>>>>>>>>>>>>>>\n", temp_width.size());
	for(int i = 0; i < temp_width.size(); i++)
	{
		printf("temp_width[%d]: s%d:0x%x\n", i, temp_width[i].reg, temp_width[i].off);
	}
	*/

	if( is_fft2d )
	{
		width.push_back(temp_width[0]);
		width.push_back(VAR_INFO(5, 0x1c));
		width.push_back(temp_width[1]);
		width.push_back(VAR_INFO(5, 0x20));
	}
	else
	{
		if(temp_width.size() == 1)
			width.push_back(temp_width[0]);
	}

#ifdef DEBUG
	printf("============width size = %d==============\n", width.size());
#endif
	// width.size() == 2 means WA & HA are the same, so push width[0] twice
	for(int i = width.size(); i < 4; i++)
		width.push_back(width[0]);		// HB = WA
	char w_label[4][3] = {"WA", "WB", "HA", "HB"};
	for(int i = 0; i < width.size(); i++)
	{
#ifdef DEBUG
		printf("width No.%d, s%d:0x%x\n",i, width[i].reg, width[i].off);
#endif
		records.push_back(Record(0, width[i].reg, width[i].off, w_label[i], sizeof(int), r_idx++));
	}
	r_idx = 8;

	if( is_fft2d )
	{
		// XXX: mock for FFT
		matrix_base.push_back(VAR_INFO(5, 0xc));
		matrix_base.push_back(VAR_INFO(5, 0x10));
		matrix_base.push_back(VAR_INFO(5, 0x8));
	}

	// display matrix
#ifdef DEBUG
	printf("=========matrix_base size = %d===========\n", matrix_base.size());
#endif
	char m_label[3][8] = {"MatrixA", "MatrixB", "MatrixC"};
	for(int i = 0; i < matrix_base.size(); i++)
	{
		int direction = (i == (matrix_base.size() - 1) ? 1 : 0);
#ifdef DEBUG
		printf("matrix %d, base reg[%d], offset 0x%x\n", i, matrix_base[i].reg, matrix_base[i].off);
#endif
		records.push_back(Record(direction, matrix_base[i].reg, matrix_base[i].off, m_label[i], sizeof(float), r_idx++));
	}
	r_idx = 12;

#ifdef DEBUG
	printf("============temp size = %d==============\n", temp_var.size());
#endif
	char t_label[10][6] = {"TEMP0", "TEMP1", "TEMP2", "TEMP3", "TEMP4", "TEMP5", "TEMP6", "TEMP7", "TEMP8", "TEMP9"};
	for(int i = 0; i < temp_var.size(); i++)
	{
#ifdef DEBUG
		printf("temp_var No.%d, s%d:0x%x\n",i, temp_var[i].reg, temp_var[i].off);
#endif
		records.push_back(Record(0, temp_var[i].reg, temp_var[i].off, t_label[i], sizeof(float), r_idx++));
	}

	if( is_fft2d )
	{
		func_args.push_back(temp_width[2]);
		func_args.push_back(temp_width[3]);
		records.push_back(Record(0, 5, temp_width[2].off, "ARG0", sizeof(int), r_idx++));
		records.push_back(Record(0, 5, temp_width[3].off, "ARG1", sizeof(int), r_idx++));
	}

	// sort records by direction
	stable_sort(records.begin(), records.end());

	printf("============records size = %d==============\n", records.size());
	for(int i = 0; i < records.size(); i++)
	{
		printf("record %d, direction: %d, label: %s, value: s%d:0x%x, length: %d, type: %d\n", i, records[i].getDirection(), records[i].getLabel(), records[i].getStartAddr(), records[i].getStartOffset(), records[i].getLength(), records[i].getDataType());
	}
}

void VBlockAnalyzer::AnalyzeDataFlows()
{
	map<XTMemAddr, XTMemAddr>::iterator lit = loops.begin();
	while(lit != loops.end())
	{
		__GetDefUseChain(lit->first);
		__GetLDInfo(lit->first);
		__GetLoopInfo(lit->first);
		__GetDataInfo(lit->first);
		analyzed_vblocks.insert(lit->first);
		if(lit->first != lit->second && (analyzed_vblocks.find(lit->second) == analyzed_vblocks.end()))
		{
			__GetDefUseChain(lit->second);
			__GetLDInfo(lit->second);
			__GetDataInfo(lit->second);
			analyzed_vblocks.insert(lit->second);
		}
		lit++;
	}

	__ProfileCollector();
	
	vblock_it vit = hot_vblocks.begin();
	while(vit != hot_vblocks.end())
	{
		__GetDefUseChain(vit->first);
		__VblockFilter(vit->first);
		vit++;
	}
}

VBlockAnalyzer::VAR_INFO VBlockAnalyzer::__GetLoopBoundGeneral(XTMemAddr entry)
{
	stack<TRACE_NODE> trace;
	VAR_INFO res;

	VBlock::vb_iterator vit = hot_vblocks[entry]->begin();

	int i = 0;		// VInst number
	while(vit != hot_vblocks[entry]->end())
	{
		Opcode op = (*vit)->getOpcode();
		DataType dt = (*vit)->getDataType();

		// find out loop index and loop bound
		if(op == OP_BRANCH)
		{
			//printf("---------Analyze BRANCH No.%d-----------\n", i);
			TRACE_NODE *node;
			bool flag = false;
			for(int k = 0; k < use[i].size(); k++)
			{
				if(use[i][k].reg != 0)
				{
					node = new TRACE_NODE(i, use[i][k]);
					trace.push(*node);
				}
			}

			int j = i;
			while(!trace.empty())
			{
				Operand opr;
				DataType t;
				XTInt32 u = __LookUpLatestDef(entry, j, trace.top(), opr, t);

				switch(u)
				{
					case -1:	// not found
						trace.pop();
						break;
					case 0:		// regular
						trace.pop();
						for(int k = 0; k < use[j].size(); k++)
						{
							node = new TRACE_NODE(j, use[j][k]);
							if(!((node->opr).type == Operand::VREG_USE && (node->opr).reg == 0))
							{
								trace.push(*node);
							}
						}
						break;
					case 1:		// LI
						trace.pop();
						break;
					case 2:		// GET
						trace.pop();
						node = new TRACE_NODE(j, use[j][0]);
						trace.push(*node);
						break;
					case 3:		// LD
						{
							// clear the trace and return the first ld_info
							while(!trace.empty())
								trace.pop();

							// there should be only 1 source of LD
							assert(ld_info[j].src.size() == 1);

							res.reg = ld_info[j].src[0].reg;
							res.off = ld_info[j].src[0].off;
							break;
						}
				}
			}
		}
		i++;
		vit++;
	}
	return res;
}

// added by zhangyichao, 2010-4-12
void VBlockAnalyzer::LoopBoundAnalyzer(VBlock *vb, RegNum &reg, XTInt32 &off)
{
	// There must be no hot_vblocks when called now.
	// because this function will be only called at static analysis phase
	assert(hot_vblocks.size() == 0);

	XTMemAddr entry = vb->enterSPC();
	VAR_INFO bound;

	hot_vblocks[entry] = vb;
	__GetDefUseChain(entry);
	__GetLDInfoGeneral(entry);
	bound = __GetLoopBoundGeneral(entry);

	reg = bound.reg;
	off = bound.off;

	hot_vblocks.clear();
}

void VBlockAnalyzer::__VblockFilter(XTMemAddr entry)
{
	ld_info.clear();
	st_info.clear();
	//map<XTInt32, LD_INFO> ld_info;		// map<VInst No. , LD_INFO>
	//map<XTInt32, ST_INFO> st_info;		// map<VInst No. , ST_INFO>
	stack<TRACE_NODE> trace;			// analyze trace
	vector<XTInt32> del_insts;
	vector<XTInt32> inst_tag;	// tag each vinst, 0: no modify; 1: del; 2: modify LD; 3: modify ST
	map<XTInt32, OPR_TAG> ld_tag;
	map<XTInt32, OPR_TAG> st_tag;
	map<XTInt32, DataType> ld_type;
	map<XTInt32, DataType> st_type;
	int i = 0;

	inst_tag.resize(hot_vblocks[entry]->size());

	VBlock::vb_iterator vit = hot_vblocks[entry]->begin();
	while(vit != hot_vblocks[entry]->end())
	{
		inst_tag[i] = 0;
		Opcode op = (*vit)->getOpcode();
		DataType type = (*vit)->getDataType();

		if(op == OP_LD)
		{
			//printf("-----Start to filter LD No.%d-----\n", i);
			del_insts.clear();
			ld_info[i].dst = (*vit)->getOperand(3);
			ld_info[i].imm = (*vit)->getOperand(2).imm;
			TRACE_NODE *node = new TRACE_NODE(i, use[i][0]);
			trace.push( *node );
			int j = i;
			while(!trace.empty())
			{
				Operand opr;
				DataType t;
				XTInt32 u = __LookUpLatestDef(entry, j, trace.top(), opr, t);

				switch(u)
				{
					case -1:	// def not found
						{
							//assert(0 && "LD error!");
							ld_info[i].src.push_back(VAR_INFO(trace.top().opr.reg, -1));
							trace.pop();
							break;
						}
					case 0:
						{
							trace.pop();
							del_insts.push_back(j);
							for(int k = 0; k < use[j].size(); k++)
							{
								node = new TRACE_NODE(j, use[j][k]);
								trace.push(*node);
							}
							break;
						}
					case 1:	// LI
						{
							del_insts.push_back(j);
							// it seems LI inst come first all the time
							// and if VAR_INFO is modified later, there will be a segmentation fault...
							// so I set reg = 5 directly here...
							ld_info[i].src.push_back(VAR_INFO(5, opr.imm));
							trace.pop();
							break;
						}
					case 2:	// GET
						{
							del_insts.push_back(j);
							trace.pop();
							if(use[j][0].reg == 5)
							{
								//ld_info[i].src.push_back(VAR_INFO(use[j][0].reg, -1));
							}
							else
							{
								node = new TRACE_NODE(j, use[j][0]);
								trace.push(*node);
							}
							break;
						}
					case 3:	// LD
						{
							del_insts.push_back(j);
							trace.pop();
							node = new TRACE_NODE(j, use[j][0]);
							trace.push(*node);
							break;
						}
				}
			}

			//assert(del_insts.size() <= 6);

			bool flag = false;
			OPR_TAG tag;

			// run filter for this LD
			for(int l = 0; (l < ld_info[i].src.size() && flag == false); l++)
			{
				// check index
				vector<VAR_INFO>::iterator var_it = index.begin();

				while(var_it != index.end() && flag == false)
				{
					int k = var_it - index.begin();
					if(ld_info[i].src[l] == *var_it)
					{
						flag = true;
						tag = (OPR_TAG)k;
					}
					var_it++;
				}

				// check matrix_base
				var_it = matrix_base.begin();
				while(var_it != matrix_base.end() && flag == false)
				{
					int k = var_it - matrix_base.begin();
					if(ld_info[i].src[l] == *var_it)
					{
						flag = true;
						tag = (OPR_TAG)(MatrixA + k);
					}
					var_it++;
				}

				// check width
				var_it = width.begin();
				while(var_it != width.end() && flag == false)
				{
					int k = var_it - width.begin();
					if(ld_info[i].src[l] == *var_it)
					{
						flag = true;
						tag = (OPR_TAG)(WA + k);
					}
					var_it++;
				}

				// check temp_var
				var_it = temp_var.begin();
				while(var_it != temp_var.end() && flag == false)
				{
					int k = var_it - temp_var.begin();
					if(ld_info[i].src[l] == *var_it)
					{
						flag = true;
						tag = (OPR_TAG)(TEMP0 + k);
					}
					var_it++;
				}

				// check func_args
				var_it = func_args.begin();
				while(var_it != func_args.end() && flag == false)
				{
					int k = var_it - func_args.begin();
					if(ld_info[i].src[l] == *var_it)
					{
						flag = true;
						tag = (OPR_TAG)(ARG0 + k);
					}
					var_it++;
				}
			}

			if(del_insts.size() > 6)
				flag = false;

			if(flag)
			{
				//cout<<"Filter LD No."<<i<<endl;
				inst_tag[i] = 2;
				ld_tag[i] = tag;
				ld_type[i] = type;
				for(int k = 0; k < del_insts.size(); k++)
				{
					//cout<<"tag No."<<del_insts[k]<<endl;
					inst_tag[del_insts[k]] = 1;
				}
			}
		}// end of OP_LD

		if(op == OP_ST)
		{
			//printf("-----Start to filter ST No.%d-----\n", i);
			del_insts.clear();
			st_info[i].src = (*vit)->getOperand(1);
			st_info[i].imm = (*vit)->getOperand(3).imm;
			TRACE_NODE *node = new TRACE_NODE(i, use[i][1]);
			trace.push( *node );
			int j = i;
			while(!trace.empty())
			{
				Operand opr;
				DataType t;
				XTInt32 u = __LookUpLatestDef(entry, j, trace.top(), opr, t);

				switch(u)
				{
					case -1:	// def not found
						{
							//assert(0 && "Filter ST should always found!");
							trace.pop();
							break;
						}
					case 0:
						{
							trace.pop();
							del_insts.push_back(j);
							for(int k = 0; k < use[j].size(); k++)
							{
								node = new TRACE_NODE(j, use[j][k]);
								trace.push(*node);
							}
							break;
						}
					case 1:	// LI
						{
							st_info[i].dst.push_back(VAR_INFO(5, opr.imm));
							//st_info[i].dst.back().off = opr.imm;
							del_insts.push_back(j);
							trace.pop();
							break;
						}
					case 2:	// GET
						{
							del_insts.push_back(j);
							trace.pop();
							if(use[j][0].reg == 5)
							{
							//st_info[i].dst.push_back(VAR_INFO(use[j][0].reg, -1));
							}
							else
							{
							node = new TRACE_NODE(j, use[j][0]);
							trace.push(*node);
							}
							break;
						}
					case 3:	// LD
						{
							trace.pop();
							for(int k = 0; k < ld_info[j].src.size(); k++)
							{
								if(ld_info[j].src[k].reg == 5)
								{
									st_info[i].dst.push_back(ld_info[j].src[k]);
								}
								else
								{
									Operand temp_opr(Operand::SREG_USE);
									temp_opr.reg = ld_info[j].src[k].reg;
									node = new TRACE_NODE(j, temp_opr);
									trace.push(*node);
								}
							}
							break;
						}
				}
			}

			//assert(del_insts.size() <= 6);

			bool flag = false;
			OPR_TAG tag;

			// run filter for this ST
			for(int l = 0; (l < st_info[i].dst.size() && flag == false); l++)
			{
				// check index
				vector<VAR_INFO>::iterator var_it = index.begin();

				while(var_it != index.end() && flag == false)
				{
					int k = var_it - index.begin();
					if(st_info[i].dst[l] == *var_it)
					{
						flag = true;
						tag = (OPR_TAG)k;
					}
					var_it++;
				}

				// check matrix_base
				var_it = matrix_base.begin();
				while(var_it != matrix_base.end() && flag == false)
				{
					int k = var_it - matrix_base.begin();
					if(st_info[i].dst[l] == *var_it)
					{
						flag = true;
						tag = (OPR_TAG)(MatrixA + k);
					}
					var_it++;
				}

				// check width
				var_it = width.begin();
				while(var_it != width.end() && flag == false)
				{
					int k = var_it - width.begin();
					if(st_info[i].dst[l] == *var_it)
					{
						flag = true;
						tag = (OPR_TAG)(WA + k);
					}
					var_it++;
				}

				// check temp_var
				var_it = temp_var.begin();
				while(var_it != temp_var.end() && flag == false)
				{
					int k = var_it - temp_var.begin();
					if(st_info[i].dst[l] == *var_it)
					{
						flag = true;
						tag = (OPR_TAG)(TEMP0 + k);
					}
					var_it++;
				}

				// check func_args
				var_it = func_args.begin();
				while(var_it != func_args.end() && flag == false)
				{
					int k = var_it - func_args.begin();
					if(st_info[i].dst[l] == *var_it)
					{
						flag = true;
						tag = (OPR_TAG)(ARG0 + k);
					}
					var_it++;
				}
			}

			if(del_insts.size() > 6)
				flag = false;

			if(flag)
			{
				//cout<<"Filter ST No."<<i<<endl;
				inst_tag[i] = 3;
				st_tag[i] = (OPR_TAG)tag;
				st_type[i] = type;
				for(int k = 0; k < del_insts.size(); k++)
				{
					//cout<<"tag No."<<del_insts[k]<<endl;
					inst_tag[del_insts[k]] = 1;
				}
			}
		}// end of OP_ST
		i++;
		vit++;
	}

	// delete redundant VInsts and modify LD
	i = 0;
	vit = hot_vblocks[entry]->begin();
	while(vit != hot_vblocks[entry]->end())
	{
		if(inst_tag[i] == 1)	// delete it
		{
			//printf("erase No.%d\n", i);
			hot_vblocks[entry]->erase(vit);
		}
		else if(inst_tag[i] == 2)	// modify this LD
		{
			VInst *inst = MOV_T_R(ld_tag[i], ld_info[i].dst.reg, ld_type[i]);
			//printf("replace No.%d\n", i);
			vit = hot_vblocks[entry]->erase(vit);
			vit = hot_vblocks[entry]->insert(vit, inst);
			vit++;
		}
		else if(inst_tag[i] == 3)	// modify this ST
		{
			VInst *inst = MOV_R_T(st_info[i].src.reg, st_tag[i], st_type[i]);
			//printf("replace No.%d\n", i);
			vit = hot_vblocks[entry]->erase(vit);
			vit = hot_vblocks[entry]->insert(vit, inst);
			vit++;
		}
		else
		{
			vit++;
		}
		i++;
	}
}

void VBlockAnalyzer::DumpEntries()
{
	const char *script_d;
	char fpath[255];
	char fname[255];
	char str_entry[12];

	script_d = (char *)getenv("SCRIPT_D");

	assert(script_d);

	FILE *output;

	// TODO: may be modified...
	// enter & exit
	map<XTMemAddr, XTMemAddr>::iterator mit = loops.end();
	mit--;
	enter = mit->second;
	exit = mit->first;

	printf("enter = 0x%x, exit = 0x%x\n", enter, exit);

	strcpy(fpath, script_d);
	strcat(fpath, "/Entry/entries");
	output = fopen(fpath, "w");

	assert(output);

	fwrite((void *)&enter, sizeof(XTMemAddr), 1, output);
	fwrite((void *)&exit, sizeof(XTMemAddr), 1, output);

	fclose(output);
}

void VBlockAnalyzer::DumpRecords()
{
	const char *script_d;
	char fpath[255];
	char fname[255];
	char str_entry[12];

	script_d = (char *)getenv("SCRIPT_D");

	assert(script_d);

	FILE *output;

	Record *record;
	strcpy(fpath, script_d);
	sprintf(str_entry, "0x%08x", enter);
	strcat(fpath, "/Records/");
	strcat(fpath, str_entry);
	strcat(fpath, ".records");
	output = fopen(fpath, "w");
	assert(output);

	for(int i = 0; i < records.size(); i++)
	{
		fwrite((void *)&(records[i]), 1, sizeof(Record), output);
	}

	fclose(output);
}

void VBlockAnalyzer::DumpVBlocksText()
{
	const char *script_d;
	char fpath[255];
	char fname[255];
	char str_entry[12];

	script_d = (char *)getenv("SCRIPT_D");

	assert(script_d);

	strcpy(fpath, script_d);
	strcat(fpath, "/IR/text_vblock");
	ofstream output2(fpath);
	assert(output2);
	vblock_it vit = hot_vblocks.begin();
	while(vit != hot_vblocks.end())
	{
		output2<<"entry: 0x"<<hex<<vit->first<<endl;
		vit->second->print(output2);
		output2<<"next: 0x"<<hex<<vit->second->nextSPC()<<dec<<endl;
		vit++;
	}
	output2.close();
}

void VBlockAnalyzer::DumpVBlocksByte()
{
	const char *script_d;
	char fpath[255];
	char fname[255];
	char str_entry[12];

	script_d = (char *)getenv("SCRIPT_D");

	assert(script_d);
	
	FILE *output;

	// Dump vblocks in byte code
	strcpy(fpath, script_d);
	strcat(fpath, "/IR/");
	vblock_it vit = hot_vblocks.begin();
	while(vit != hot_vblocks.end())
	{
		int n = 0;
		XTMemAddr next = vit->second->nextSPC();
		sprintf(str_entry, "0x%08x", vit->first);
		strcpy(fname, fpath);
		strcat(fname, str_entry);
		ofstream output2(fname);

		assert(output2);

		output2.write((char *)&next, sizeof(XTMemAddr));
		//printf("entry = 0x%x, time = %d, next = 0x%x\n", vit->first, block_count[vit->first], next);

		VBlock::vb_iterator iit = vit->second->begin();
		while(iit != vit->second->end())
		{
			int size = (*iit)->getSize();
			output2.write((char *)&size, sizeof(int));
			output2.write((char *)(*iit), (*iit)->getSize());
			n++;
			iit++;
		}
		output2.close();
		vit++;
	}

	/*
	// Dump def-use info
	output = fopen("def_chain", "w");

	for(int i = 0; i < def.size(); i++)
	{
		fprintf(output, "No.%d: ", i);
		for(int j = 0; j < def[i].size(); j++)
		{
			switch(def[i][j].type)
			{
				case Operand::SREG_DEF:
					fprintf(output, " s%d,", def[i][j].reg);
					break;
				case Operand::VREG_DEF:
					fprintf(output, " v%d,", def[i][j].reg);
					break;
				case Operand::FREG_DEF:
					fprintf(output, " f%d,", def[i][j].reg);
					break;
				default:
					printf("type = %d\n", def[i][j].type);
					assert(0 && "wrong oprand type in def_chain!");
			}
		}
		fprintf(output, "\n");
	}
	fclose(output);

	output = fopen("use_chain", "w");

	for(int i = 0; i < use.size(); i++)
	{
		fprintf(output, "No.%d: ", i);
		for(int j = 0; j < use[i].size(); j++)
		{
			switch(use[i][j].type)
			{
				case Operand::SREG_USE:
					fprintf(output, " s%d,", use[i][j].reg);
					break;
				case Operand::VREG_USE:
					fprintf(output, " v%d,", use[i][j].reg);
					break;
				case Operand::FREG_USE:
					fprintf(output, " f%d,", use[i][j].reg);
					break;
				default:
					printf("type = %d\n", use[i][j].type);
					assert(0 && "wrong oprand type in use_chain!");
			}
		}
		fprintf(output, "\n");
	}
	fclose(output);
	*/
}

